package com.xy6.struct.array;

import com.xy6.algo.search.SearchBinary;
import com.xy6.algo.sort.SortQuick;

/**
 * 数组
 * <pre>
 * 对数据进行增、删、查
 * 
 * 一种基本数据类型。
 * 以线性结构来存储固定数量的数据类型相同的数据。
 * 数组是一段连续的内存，物理连续或逻辑连续。
 * 数组不仅是一个数据的容器，还提供对数据的操作方法，如检索、插入、删除、排序。
 * 数组分为：无序数组、有序数组。无序、有序指数组中元素是否按一定顺序排列。
 * 无序数组，优点：在指定位置插入快，缺点：查找指定元素慢
 * 有序数组，优点：查找指定元素快（二分查找，O(logn)），缺点：插入元素慢
 * 典型操作：排序、查找。
 * 排序算法：冒泡（O(n^2)），选择（O(n^2)），插入（O(n^2)），
 * 		归并（O(nlgn)），快速（O(nlgn)），堆排（O(nlgn)），桶排（O(n+c)（C=N*(logN-logM)））
 * 查找算法：顺序，二分，二叉树，块查，哈希，插值
 * </pre>
 * 
 * @author zhang
 * @since 2017-08-25
 */
public class MyArray {

	public static void main(String[] args) {
		int[] nums = new int[]{2, 1, 3, 6, 5};
		print(nums);
		
		nums = insert(nums, 2, 10);
		print(nums);
		
		nums = removeByIndex(nums, 2);
		print(nums);
		
		nums = removeByObject(nums, 6);
		print(nums);
		
		int elem = get(nums, 2);
		System.out.println(elem);
		
		int index = search(nums, 2);
		System.out.println(index);
		
		SortQuick.sort(nums);
		print(nums);
		
		index = SearchBinary.search(nums, 3);
		System.out.println(index);
	}
	
	/**
	 * 在数组中某个位置插入一个元素
	 * 
	 * @param nums
	 * @param index
	 * @param data
	 */
	public static int[] insert(int[] nums, int index, int data){
		if(index < 0 || index > nums.length){
			return nums;
		}
		int[] newnums = new int[nums.length + 1];
		for(int i=0; i<index; i++){
			newnums[i] = nums[i];
		}
		newnums[index] = data;
		for (int i = index; i < nums.length; i++) {
			newnums[i + 1] = nums[i];
		}
		return newnums;
	}
	
	/**
	 * 输出集合的元素
	 * 
	 * @param nums
	 */
	public static void print(int[] nums){
		for (int i = 0; i < nums.length; i++) {
			System.out.print(nums[i] + " ");
		}
		System.out.println();
	}
	
	public static int[] removeByIndex(int[] nums, int index){
		if(index < 0 || index >= nums.length){
			return nums;
		}
		int[] newnums = new int[nums.length - 1];
		for(int i=0; i<index; i++){
			newnums[i] = nums[i];
		}
		for (int i = index + 1; i < nums.length; i++) {
			newnums[i - 1] = nums[i];
		}
		return newnums;
	}
	
	public static int[] removeByObject(int[] nums, int data){
		int index = search(nums, data);
		if(index == -1){
			return nums;
		}
		return removeByIndex(nums, index);
	}
	
	public static int get(int[] nums, int index){
		return nums[index];
	}
	
	public static int search(int[] nums, int data){
		for(int i=0; i<nums.length; i++){
			if(nums[i] == data){
				return i;
			}
		}
		return -1;
	}

}
